CS 5010: Problem Set 8

Out: Monday, March 14, 2016

Due: Monday, March 21, 2016 at 5pm local time.

Corrected: Wednesday, March 16 (examples for least-argument-yielding)

Corrected: Thursday, March 17 (added WHERE clause for least-argument-yielding)

The goal of this problem set is to give you practice using most of what you've learned this semester.

Some of these problems may not be easy, so start early and leave yourself plenty of time to finish them.

You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use higher order functions such as filter and map whenever they are helpful. As before, you will be penalized for failing to use these when they are "obviously" applicable.

Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information. We expect that your data definitions, interpretations, and invariants will be sufficient to explain the meaning of every quantity in your program. You will be judged on the adequacy of these deliverables.

For each function that you write using general recursion, you must deliver:

A STRATEGY line describing briefly what you are recurring on. If the the value returned by the recursive call is not the final answer, describe briefly what you do with the result of the recursive call to obtain the final answer. Remember: the strategy is a tweet-sized description of how your function works.
A HALTING MEASURE, specifying the quantity that you are proposing as a halting measure.
A TERMINATION ARGUMENT, giving an informal proof that your proposed halting measure is always a non-negative integer and that it decreases at every recursive call.
If your function fails to terminate for some inputs, explain which inputs those are. (For this particular problem set, we don't think there should be any such functions, but we could be wrong about that. If we are wrong about that, it's your responsibility to tell us about it.)

The example files contain numerous examples of the first three of these deliverables.

You will be judged on the correctness of your halting measures and termination arguments.

If you really need to do so, it is ok to write two mutually-recursive functions using general recursion. If you do this, you need make sure that your halting measure decreases on EVERY recursive call to the function, even if that call comes via the other function.

As before, if your function does not fulfill its purpose for all combinations of arguments that satisfy the contract, then you must write an invariant that documents what additional assumptions your function makes about its arguments.

Not everything on this problem set requires the use of invariants or the use of general recursion. Part of your task is to figure out when you need these things and when you do not. Remember, it is the purpose statement that determines whether or not you need to state an invariant.

Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, strategies, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS08

As usual, the rubric for grading is here.

The first problem refers to the Fibonacci sequence f₀, f₁, f₂, ... defined by

f₀ is 0
f₁ is 1
if i > 1, then f_i is f_i-1 + f_i-2

The first problem also refers to monotonic functions. If a function g is monotonic, and i < j, then g(i) < g(j).

The second and third problems refer to symbols, which are just Racket symbols. You have already read about them in Part IV of the textbook.

(search). For this problem, you will deliver a file named search.rkt that provides the following four functions:

;;; fib : NonNegInt -> NonNegInt
;;; GIVEN: i
;;; RETURNS: the Fibonacci number f_i (defined above)
;;; EXAMPLES:
;;;     (fib 0)  => 0
;;;     (fib 10) => 55
;;;
;;; next-fibonacci-number : Integer -> NonNegInt
;;; GIVEN: any integer n
;;; RETURNS: the smallest Fibonacci number greater than or equal to n
;;; EXAMPLES:
;;;     (next-fibonacci-number -226) => 0
;;;     (next-fibonacci-number   50) => 55
;;;
;;; least-result-as-large-as : (NonNegInt -> Integer) Integer -> Integer
;;; GIVEN: a function f and an integer n
;;; WHERE: f is monotonic
;;; RETURNS: the smallest value of (f i) such that
;;;     i is a non-negative integer and (f i) is greater than or equal to n
;;; EXAMPLES:
;;;     (least-result-as-large-as fib -226)  => 0
;;;     (least-result-as-large-as fib   50)  => 55
;;;     (least-result-as-large-as sqr  100)  => 100
;;;     (least-result-as-large-as sqr  500)  => 529
;;;
;;; least-argument-yielding : (NonNegInt -> Integer) Integer -> Integer
;;; GIVEN: a function f and an integer n
;;; WHERE: there exists some non-negative integer k such that (f k)
;;;     is greater than or equal to n
;;; RETURNS: the smallest value of i such that
;;;     i is a non-negative integer and (f i) is greater than or equal to n
;;; EXAMPLES:
;;;     (least-argument-yielding fib -226)  => 0
;;;     (least-argument-yielding fib   50)  => 10
;;;     (least-argument-yielding sqr  100)  => 10
;;;     (least-argument-yielding sqr  500)  => 23
;;;     (least-argument-yielding (lambda (i) (- (sqr i) (* 20 i))) 100) => 25

Be sure to spell the names of your functions correctly, both in their definitions and in your list of provided functions.

(freevars). For this problem, you will deliver a file named freevars.rkt that provides functions to compute the free and bound variables of programs written in a simple programming language. That language's syntax is defined as follows:

;;; An Expr is one of
;;;     -- Integer
;;;     -- Symbol
;;;     -- Call
;;;
;;; Interpretation: an Expr represents an integer, an identifier,
;;; or a function call.
;;;
;;; A Call is
;;;     (cons Expr ListOfExpr)
;;;
;;; Interpretation: a Call represents a function call in which
;;; the value of the first expression in the Call must be a function,
;;; which is called on the values of the expressions in the ListOfExpr.
;;;
;;; A Defn is
;;;     (list 'def (cons Symbol ListOfSymbol) Expr)
;;;
;;; Interpretation: a Defn represents a function.
;;; The lone Symbol is the name of the function, and the symbols
;;; in the ListOfSymbol are the names of its arguments.  The Expr
;;; represents the value to be returned by the function.
;;; (Note that functions with no arguments can be defined.)
;;;
;;; A Program is
;;;     (cons Defn ListOfDefn)
;;; Interpretation: a program is a non-empty list of definitions.
;;; When the program is run, the function defined by the first
;;; definition will be called with arguments obtained in some
;;; OS-dependent manner we needn't discuss here.
;;;
;;; A ListOfSymbol is
;;;     -- empty
;;;     -- (cons Symbol ListOfSymbol)
;;;
;;; A ListOfExpr is
;;;     -- empty
;;;     -- (cons Expr ListOfExpr)
;;; 
;;; A ListOfDefn is
;;;     -- empty
;;;     -- (cons Defn ListOfDefn)

A SetOfSymbol is a ListOfSymbol in which no symbol appears more than once.

The set of free variables of an Expr E is the set of symbols that occur within E. Formally:

If E is an Integer, then its set of free variables is the empty set.
If E is a Symbol I, then its set of free variables consists of I and nothing else.
If E is a Call of the form (cons E₀ (list E₁ ... E_n)), then its set of free variables is the union of the sets of free variables for E₀, E₁, ... E_n.

For this particular programming language, the set of bound variables of an expression is always empty.

The set of bound variables of a Defn of the form

    (list 'def (cons I₀ (list I₁ ... I_n))
          E)

is the set {I₀, I₁, ... I_n}. The set of free variables of that definition is the set difference between the set of free variables of E and the definition's set of bound variables.

A program's set of free variables is the set difference between the union of the sets of free variables of its definitions and the set of function names defined by those definitions. A program's set of bound variables is the union of the sets of bound variables of its definitions.

Your freevars.rkt file must provide the following nine functions:

;;; expr-free    : Expr    -> SetOfSymbol
;;; defn-free    : Defn    -> SetOfSymbol
;;; program-free : Program -> SetOfSymbol
;;; GIVEN: (respectively) an expression, definition, or program
;;; RETURNS: the set of free variables
;;;     of that expression, definition, or program
;;; EXAMPLES: see below
;;;
;;; expr-bound    : Expr    -> SetOfSymbol
;;; defn-bound    : Defn    -> SetOfSymbol
;;; program-bound : Program -> SetOfSymbol 
;;; GIVEN: (respectively) an expression, definition, or program
;;; RETURNS: the set of bound variables
;;;     of that expression, definition, or program
;;; EXAMPLES: see below
;;;
;;; expr-undefined    : Expr    SetOfSymbol -> SetOfSymbol
;;; defn-undefined    : Defn    SetOfSymbol -> SetOfSymbol
;;; program-undefined : Program SetOfSymbol -> SetOfSymbol
;;; GIVEN: (respectively) an expression, definition, or program
;;;     and a set of symbols representing the set of identifiers
;;;     that are defined by the expression's, definition's, or
;;;     program's context
;;; RETURNS: the set of free variables of that expression, definition,
;;;     or program minus the set of identifiers defined by its context
;;; EXAMPLES: see below

(define expr1 '(+ x y 3))
(define expr2 (list '* expr1 expr1 'z))
(define defn1 (list 'def '(f x y) expr2))
(define defn2 '(def (g a z) (f z a)))
(define pgm1 (list defn1 defn2))

(expr-free expr1)       ; => { +, x, y }
(expr-free expr2)       ; => { *, +, x, y, z }
(defn-free defn1)       ; => { *, +, z }
(defn-free defn2)       ; => { f }
(program-free pgm1)     ; => { *, +, z }

(expr-bound expr1)      ; => { }
(expr-bound expr2)      ; => { }
(defn-bound defn1)      ; => { f, x, y }
(defn-bound defn2)      ; => { g, a, z }
(program-bound pgm1)    ; => { a, f, g, x, y, z }

(expr-undefined expr1   '(+ - * f g x y))    ; => { }
(expr-undefined expr2   '(+ - * f g x y))    ; => { z }
(defn-undefined defn1   '(+ - * f g))        ; => { z }
(defn-undefined defn2   '(+ - * f g))        ; => { }
(program-undefined pgm1 '(+ - * f g))        ; => { z }

(pretty). For this problem, you will deliver a file named pretty.rkt that defines a pretty-printer for the programming language defined in the previous problem. More precisely, you are to provide the following function:
```
;;; program-to-strings : Program PosInt -> ListOfString
;;; GIVEN: a program and a width
;;; RETURNS: a representation of the program as a sequence of lines,
;;;     following the formatting rules described below
```
In the formatting rules below, a program fragment fits on a line if and only if a string that starts with the proper indentation for that program fragment and contains that program fragment is no longer than the given width.
1. The program is formatted by formatting each of its definitions in sequence, with one blank line (represented by an empty string) between every pair of consecutive definitions.
2. Each definition (def (I₀I₁...I_n)E) is formatted by formatting the "(def (I₀I₁...I_n)" part as described below, followed by E starting on a new line with an additional two spaces of indentation.
3. The "(def (I₀I₁...I_n)" part of a definition is formatted on a single line if it will fit on a line no longer than the given width, with no indentation.
4. If the function header shown above will not fit on a single line, but the "(def (I₀I₁" part will fit on a single line (with no indentation), and all of the remaining arguments will fit if placed on separate lines and indented so they line up under the first argument, and the parenthesis that closes the list of arguments will also fit on the line containing the last argument, then the function header is formatted that way.
5. If the function header will not fit within the width when formatted in either of the two preceding ways, then the "(def (I₀" part is formatted on a single line (with no indentation), and every one of the remaining arguments is placed on a separate line, indented to line up under I₀, with the parenthesis that closes the list of arguments on the same line as the last argument.
6. The function body E is indented two spaces.
7. If an expression E will fit on a single line, including its indentation, then it is formatted that way.
8. If a call of the form (E₀E₁...E_n) will not fit within a single line when indented, but the "(E₀E₁" part will fit, then that much of the call is placed on a single line and each of the remaining argument expressions begins on a separate line, indented to line up under E₁, and the closing parenthesis is placed on the same line as the last argument expression.
9. If the "(E₀E₁" part of a call will not fit within a single line when indented, but the "(E₀" part does, then that much of the call expression gets a line all to itself, and each of the argument expressions begins on a separate line, indented to line up under E₀.
10. If the "(E₀" part of a call will not fit within a single line when indented, then E₀ is formatted with one extra space of indentation using as many lines as necessary, the space immediately preceding the start of E₀ is replaced by the opening parenthesis of the call, and each of the argument expressions begins on a separate line, indented to line up under E₀.
11. No left parenthesis is ever followed by a space, and no left parenthesis ever appears at the end of a line. No right parenthesis is ever preceded by a space, and no right parenthesis ever appears at the start of a line.
12. None of the lines end with a space.
13. The only blank lines are the blank lines that separate definitions. Those blank lines must be represented by empty strings.
14. Following these rules may result in some lines that are longer than the given width. For example, the integer 123456789012345678901234567890 will never fit within a line of length 25. For more interesting examples of overly long lines, see below.
To help you debug your program, we have provided in extras.rkt the function:
```
;;; display-strings! : ListOfString -> Void
;;; GIVEN: a list of strings
;;; EFFECT: displays the strings on separate lines
;;; RETURNS: no value
```
Be sure to download a fresh copy of extras.rkt containing this function. Here is a sample interaction, using pgm1 as defined in the previous problem statement:
```
> (display-strings! (program-to-strings pgm1 30))
(def (f x y)
  (* (+ x y 3) (+ x y 3) z))

(def (g a z)
  (f z a))
> (display-strings! (program-to-strings pgm1 25))
(def (f x y)
  (* (+ x y 3)
     (+ x y 3)
     z))

(def (g a z)
  (f z a))
```
Here is an example in which one line exceeds the given width:
```
> (display-strings! (program-to-strings pgm2 30))
(def (%vector-map1! f
                    target
                    vec
                    len)
  (loop f target vec len))

(def (loop f target vec i)
  (if (zero? i)
      target
      (let ((j (- i 1)))
           (vector-set! target
                        j
                        (f
                         (vector-ref
                          vec
                          j)))
           (loop f
                 target
                 vec
                 j))))
```
Here are some hints on this problem.
- display-strings! is to help you to debug your program, but we will be testing the lists of strings produced by program-to-strings.
- The number->string and symbol->string functions convert numbers and symbols to strings.
- If a program can be formatted within the given width while following the rules given above, then there is exactly one list of strings that satisfies the specification.
- This problem requires careful analysis of the context. You may want to design help functions that use additional context variables to keep track of the context.

Last modified: Wed Mar 16 2016